import java.util.Arrays;

public class ChaRUSort {
    /**
     * 插入排序
     * @param arr
     */
    public static void InsertSortDemo(int[] arr) {
        //插入排序是将一个数组变换为一个有序的数组和一个无序数组，每次将无序数组插入到有序的数组中，并调整顺序
        int  n = arr.length;
        for (int i = 1; i < n; ++i) {
            //当前要插入到有序数组中的元素
            int node = arr[i];
            //有序数组的长度 j = 0
            int j = i-1;
            while (j >=0 && arr[j] > node){
                //将数组向后移动
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j+1] = node;
        }

    }
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 3, 1, 6};

        ChaRUSort.InsertSortDemo(arr);
        System.out.println("arr = " + Arrays.toString(arr));
    }
}
